import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        //int[] nums = new int[]{1,1,1,0,0,0,1,1,1,1,0};
        //System.out.println(test.longestOnes(nums, 2));

        int[] nums = new int[]{1,1,4,2,3};
        System.out.println(test.minOperations(nums, 5));
    }

    public int longestOnes1(int[] nums, int k) {
        /**
         * 最大连续1的个数
         * 题目转换：因为数组中仅有0和1，由题得最多可以翻转k个0为1，找连续1的最大个数
         *  实质上就是找0小于等于k的最大区间，使用滑动窗口算法即可解决
         * 题目优化：
         *  为了能够快速定位到0，因此对零使用map进行存储优化
         * */
        // 1 预处理
        int n = nums.length;
        Queue<Integer> zero = new LinkedList<>();

        // 2 双指针
        int left = 0;
        int right = 0;
        int maxSize = 0;
        while(right < n) {
            // notes:由于至多可以翻转k个0为1，因此我们区间中的0少于等于k时，不用理会，仅当k满且又遇见0时再处理
            if(nums[right] == 0 && k == zero.size()) {
                if(!zero.isEmpty()) {
                    // -满且k！=0，需要出队，移动left，入队，right++
                    left = zero.poll() + 1;
                    zero.offer(right);
                } else {
                    // k==队列长度 && 对列为空，说明k==0，区间不能有一个0
                    left = right + 1;
                }
            } else {
                if(nums[right] == 0) {
                    zero.offer(right);
                }
                maxSize = Math.max(right - left + 1, maxSize);
            }
            right ++;
        }
        return maxSize;
    }

    public int longestOnes(int[] nums, int k) {
        /**
         * 最大连续1的个数
         * 题目转换：因为数组中仅有0和1，由题得最多可以翻转k个0为1，找连续1的最大个数
         *  实质上就是找0小于等于k的最大区间，使用滑动窗口算法即可解决
         * 题目优化：
         *  还不如不优化，直接写更加快！
         * */
        // 1 预处理
        int n = nums.length;

        // 2 双指针
        int left = 0;
        int right = 0;
        int maxSize = 0;
        int count = 0;
        while(right < n) {
            // -1 对当前值进行记录
            if(nums[right] == 0) {
                count ++;
            }
            // -2 处理加上right后的可能性
            if(count <= k) {
                maxSize = Math.max(right - left + 1, maxSize);
            } else {
                while(count > k) {
                    if(nums[left] == 0) {
                        count --;
                    }
                    left ++;
                }
                if(n - left + 1 < maxSize) {
                    break;
                }
            }
            right ++;
        }
        return maxSize;
    }

    public int minOperations(int[] nums, int x) {
        /**
         * 将x减到0的最小操作数
         * 转换思路即可，既然需要将nums左右两边删除数使得删除总和为0且操作数最小
         * 我们只需让留下来的数范围最大即可*/
        // 1 预处理
        int n = nums.length;
        int target = Arrays.stream(nums).sum() - x;

        // 2 双指针（在nums数组中找到和为target的最大范围子数组）
        int left = 0;
        int right = 0;
        int sum = 0;
        int maxSize = -1;
        while(right < n) {
            sum += nums[right];

            if(sum == target) {
                maxSize = Math.max(maxSize, right - left + 1);
            } else if(sum > target) {
                // -此处存在错误，因为我没有注意到x的取值，若x值大于数组和，则target为负数，此处会越界
                while(left < n && sum > target) {
                    sum -= nums[left];
                    left ++;
                }
                if(sum == target) {
                    maxSize = Math.max(maxSize, right - left + 1);
                }
            }
            right ++;
        }
        // 3 返回值
        return maxSize == -1 ? -1 : n - maxSize;
    }
}
